package BackTrack;

import MyUtils.MHUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static MyUtils.MHUtils.debug_digui;

/**
 * 从上向下，每次选1行中的1个（即1列）
 * <p>
 * 这样简化：
 * isValid 判断左上右上有没有即可，因为下方肯定没有
 * <p>
 * <p>
 * 不着急写核心代码，先把 架 写好！（类似庄总整理/删除）
 * <p>
 * <p>
 * GIT乱时，
 * 看好 "-m注释 + 后面2点"
 * <p>
 * （--amend有时候左右横移）
 */
public class N皇后51 {
    char[][] gird;
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        // String不能改，所以先用char
        char[][] gird = new char[n][n];
        this.gird = gird;
        // 初始化 全.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                gird[i][j] = '.';
            }
        }
        // 回溯 （树 每层就是"一行row"）
        backTrack(0);
        return res;
    }

    public void backTrack(int row) {
        if (row == gird.length) {
            res.add(charToList(gird));
            return;
        }

        for (int col = 0; col < gird.length; col++) {
            if (!isVaild(row, col)) {
                continue;
            }
            gird[row][col] = 'Q';
            backTrack(row + 1);
            gird[row][col] = '.';
        }
    }

    //（因为皇后从第一行向下放的，所以只判断上方即可） 左上 右上 直上
    boolean isVaild(int row, int col) {
        // 左上
        for (int i = row - 1, j = col - 1; i >= 0 & j >= 0; i--, j--) {
            if (gird[i][j] == 'Q')
                return false;
        }
        // 右上
        for (int i = row - 1, j = col + 1; i >= 0 & j < gird.length; i--, j++) {
            if (gird[i][j] == 'Q')
                return false;
        }
        // 直上
        for (int i = row - 1; i >= 0; i--) {
            if (gird[i][col] == 'Q')
                return false;
        }
        return true;
    }
    // char[][] -> List<String>
    public List<String> charToList(char[][] chars) {
        List<String> l = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            String s = "";
            for (int j = 0; j < chars.length; j++) {
                s += chars[i][j];
            }
            l.add(s);
        }
        return l;
    }

    @Test
    public void test() {
        System.out.println("\nRES: " + solveNQueens(4));
    }
}
